<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,200分)- 两个字符串间的最短路径问题（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>给定两个字符串&#xff0c;分别为字符串 A 与字符串 B。</p> 
<p>例如 A字符串为 &#34;ABCABBA&#34;&#xff0c;B字符串为 &#34;CBABAC&#34; 可以得到下图 m * n 的二维数组&#xff0c;定义原点为(0,0)&#xff0c;终点为(m,n)&#xff0c;水平与垂直的每一条边距离为1&#xff0c;映射成坐标系如下图。</p> 
<p></p> 
<p>从原点 (0,0) 到 (0,A) 为水平边&#xff0c;距离为1&#xff0c;从 (0,A) 到 (A,C) 为垂直边&#xff0c;距离为1&#xff1b;</p> 
<p>假设两个字符串同一位置的两个字符相同&#xff0c;则可以作一个斜边&#xff0c;如 (A,C) 到 (B,B) 最短距离为斜边&#xff0c;距离同样为1。</p> 
<p>作出所有的斜边如下图&#xff0c;(0,0) 到 (B,B) 的距离为&#xff1a;1 个水平边 &#43; 1 个垂直边 &#43; 1 个斜边 &#61; 3。</p> 
<p><img alt="" height="432" src="https://img-blog.csdnimg.cn/direct/8eba3ec4f6ba471991fd97a0b3cd81e0.png" width="523" /></p> 
<p></p> 
<p>根据定义可知&#xff0c;原点到终点的最短距离路径如下图红线标记&#xff0c;最短距离为9&#xff1a;</p> 
<p><img alt="" height="458" src="https://img-blog.csdnimg.cn/direct/d0072ebc837a403d926daaf0e85ea18e.png" width="533" /></p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>空格分割的两个字符串 A 与字符串 B</p> 
<ul><li>字符串不为&#34;空串&#34;</li><li>字符格式满足正则规则&#xff1a;[A-Z]</li><li>字符串长度 &lt; 10000</li></ul> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>原点到终点的最短距离</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">ABC ABC</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">3</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">ABCABBA CBABAC</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">9</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题可以通过动态规划来求解&#xff1a;</p> 
<p>我们假设dp[i][j]表示(0,0)到(i,j)的最短距离&#xff0c;那么这个最短距离只可能来自三个方向&#xff1a;</p> 
<ul><li>dp[i-1][j]&#xff0c;当前点的上方点</li><li>dp[i][j-1]&#xff0c;当前点的左边点</li><li>dp[i-1][j-1]&#xff0c;当前点的左上方点</li></ul> 
<p>而存在推导式如下&#xff1a;</p> 
<p>dp[i][j] &#61; min(dp[i-1][j]&#xff0c;dp[i][j-1]&#xff0c;<span style="color:#fe2c24;">dp[i-1][j-1]</span>) &#43; 1</p> 
<blockquote> 
 <p>另外需要注意的是&#xff0c;上面推导式dp[i-1][j-1]参与比较是有前提条件的&#xff0c;即如果(i-1, j-1)点和(i,j)点之间存在斜线相连时&#xff0c;才能将dp[i-1][j-1]带入上面推导式&#xff0c;否则不能带入。</p> 
</blockquote> 
<p></p> 
<p>并且上面推导式还可以优化&#xff0c;如果当前点可以向三个方向扩散&#xff1a;</p> 
<p></p> 
<ul><li>向右</li><li>向下</li><li>向右下</li></ul> 
<p>那么向右和向下是否有必要扩散呢&#xff1f;比如下图</p> 
<p><img alt="" height="445" src="https://img-blog.csdnimg.cn/direct/8bac7510b25741d2be9591d68bbf8893.png" width="520" /></p> 
<p>从(1,1)处可以向三个方向扩散&#xff0c;此时可以看出扩散后的三个新位置X,Y,Z&#xff0c;其中Y要比X,Z更靠近右下角点。</p> 
<p>那么有没有可能存在一种路径&#xff0c;比如Z点沿着这条路径到达右下角点更快呢&#xff1f;我们改造一下上面图示&#xff1a;</p> 
<p>假设存在下面路径&#xff0c;可以让Z点快速到达右下角点&#xff0c;此时我们可以发现&#xff0c;其实Y点也可以凭借该路径以一样的路径长度到达</p> 
<p><img alt="" height="450" src="https://img-blog.csdnimg.cn/direct/c9f58ee26faa4892bebb1914bcb4ba82.png" width="526" /></p> 
<p>因此&#xff0c;如果如果存在一条路径可以让Z快速到达右下角点&#xff0c;那么Y一定也可以借用到这条路径&#xff0c;以一样的距离到达右下角点。再给个图示例子&#xff1a;</p> 
<p><img alt="" height="444" src="https://img-blog.csdnimg.cn/direct/5f6127aa606646a2af39afe623aca33f.png" width="527" /></p> 
<p>因此&#xff0c;优化思路是&#xff0c;如果当前点可以向三个方向扩散&#xff0c;那么此时可以只扩散&#xff1a;向右下斜边方向。</p> 
<p></p> 
<p>即推导式可以变为&#xff1a;</p> 
<ul><li>如果&#xff08;i-1, j-1&#xff09;和&#xff08;i,j&#xff09;之间存在斜线相连&#xff0c;则dp[i][j] &#61; dp[i-1][j-1] &#43; 1</li><li>否则&#xff1a;dp[i][j] &#61; min(dp[i-1][j], dp[i][j-1]) &#43; 1</li></ul> 
<p></p> 
<p>本题数量级较大&#xff0c;因此如果构造一个m行n列的dp矩阵&#xff0c;那么会超出内存限制。</p> 
<p>优化思路是使用压缩数组&#xff0c;我们可以先看下下面的纯动态规划解法&#xff0c;可以发现</p> 
<p>初始化好dp数组的第一行&#xff0c;第一列后&#xff0c;我们通过两个for循环开始完成dp数组其他位置元素的求解&#xff0c;但是本质上还是逐行求解的。</p> 
<p>因此&#xff0c;我们完全只需要保留两行&#xff1a;preRow用于记录前一行的dp元素值&#xff0c;curRow用于保存当前行的dp元素值。</p> 
<p>curRow仅需要根据preRow即可完成所有元素求解。&#xff08;PS&#xff1a;curRow的第一列元素值取值即为所在行号&#xff09;</p> 
<p>这样我们就避免了dp数组记录一些过期数据。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<h5 style="background-color:transparent;">动态规划解法&#xff08;下面解法会超出内存限制&#xff0c;但是好理解&#xff0c;是后面一种压缩数组解法的基础&#xff09;</h5> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

void (async function () {
  const [A, B] &#61; (await readline()).split(&#34; &#34;);

  const m &#61; B.length;
  const n &#61; A.length;

  // dp[i][j] 记录的是(0,0)到达点(i, j)的最短路径
  const dp &#61; new Array(m &#43; 1).fill(0).map(() &#61;&gt; new Array(n &#43; 1).fill(0));

  // (0,0)到达矩阵第一行上的各点的最短路径&#xff0c;即为(0,0) -&gt; (0,j) 的直线路径
  for (let j &#61; 0; j &lt;&#61; n; j&#43;&#43;) {
    dp[0][j] &#61; j;
  }

  // (0,0)到达矩阵第一列上的各点的最短路径&#xff0c;即为(0,0) -&gt; (i,0) 的直线路径
  for (let i &#61; 0; i &lt;&#61; m; i&#43;&#43;) {
    dp[i][0] &#61; i;
  }

  for (let i &#61; 1; i &lt;&#61; m; i&#43;&#43;) {
    for (let j &#61; 1; j &lt;&#61; n; j&#43;&#43;) {
      if (A[j - 1] &#61;&#61; B[i - 1]) {
        // 如果可以走斜线&#xff0c;则选走斜线的点
        dp[i][j] &#61; dp[i - 1][j - 1] &#43; 1;
      } else {
        // 如果不能走斜线&#xff0c;则从当前点的上方点、左方点中选择一个较小值
        dp[i][j] &#61; Math.min(dp[i - 1][j], dp[i][j - 1]) &#43; 1;
      }
    }
  }

  console.log(dp[m][n]);
})();
</code></pre> 
<h5>动态规划&#43;压缩数组&#xff08;可以对比上面代码进行理解&#xff09;</h5> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

void (async function () {
  const [A, B] &#61; (await readline()).split(&#34; &#34;);

  const m &#61; B.length;
  const n &#61; A.length;

  // 初始时preRow记录第一行上各点到(0,0)点的最短距离&#xff0c;即为(0,0) -&gt; (0,j) 的直线路径
  const preRow &#61; new Array(n &#43; 1).fill(0).map((_, j) &#61;&gt; j);

  // 初始时curRow记录第二行上各点到(0,0)点的最短距离
  const curRow &#61; new Array(n &#43; 1);

  for (let i &#61; 1; i &lt;&#61; m; i&#43;&#43;) {
    // curRow[0]是指 (i, 0)点 到 (0,0)点 的最短距离&#xff0c;即为(0,0) -&gt; (i, 0) 的直线路径
    curRow[0] &#61; i;

    for (let j &#61; 1; j &lt;&#61; n; j&#43;&#43;) {
      if (A[j - 1] &#61;&#61; B[i - 1]) {
        // 如果可以走斜线&#xff0c;则选走斜线的点
        curRow[j] &#61; preRow[j - 1] &#43; 1;
      } else {
        // 如果不能走斜线&#xff0c;则从当前点的上方点、左方点中选择一个较小值
        curRow[j] &#61; Math.min(preRow[j], curRow[j - 1]) &#43; 1;
      }
    }

    // 压缩
    for (let j &#61; 0; j &lt;&#61; n; j&#43;&#43;) preRow[j] &#61; curRow[j];
  }

  console.log(curRow[n]);
})();
</code></pre> 
<h5></h5> 
<h4>Java算法源码</h4> 
<h5>动态规划解法&#xff08;下面解法会超出内存限制&#xff0c;但是好理解&#xff0c;是后面一种压缩数组解法的基础&#xff09;</h5> 
<pre><code class="language-java">import java.util.Scanner;

public class Main {
  static String A;
  static String B;
  static int m;
  static int n;

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    A &#61; sc.next();
    B &#61; sc.next();

    m &#61; B.length();
    n &#61; A.length();

    System.out.println(getResult());
  }

  public static int getResult() {
    // dp[i][j] 记录的是(0,0)到达点(i, j)的最短路径
    int[][] dp &#61; new int[m &#43; 1][n &#43; 1];

    // (0,0)到达矩阵第一行上的各点的最短路径&#xff0c;即为(0,0) -&gt; (0,j) 的直线路径
    for (int j &#61; 0; j &lt;&#61; n; j&#43;&#43;) {
      dp[0][j] &#61; j;
    }

    // (0,0)到达矩阵第一列上的各点的最短路径&#xff0c;即为(0,0) -&gt; (i,0) 的直线路径
    for (int i &#61; 0; i &lt;&#61; m; i&#43;&#43;) {
      dp[i][0] &#61; i;
    }

    for (int i &#61; 1; i &lt;&#61; m; i&#43;&#43;) {
      for (int j &#61; 1; j &lt;&#61; n; j&#43;&#43;) {
        if (A.charAt(j - 1) &#61;&#61; B.charAt(i - 1)) {
          // 如果可以走斜线&#xff0c;则选走斜线的点
          dp[i][j] &#61; dp[i - 1][j - 1] &#43; 1;
        } else {
          // 如果不能走斜线&#xff0c;则从当前点的上方点、左方点中选择一个较小值
          dp[i][j] &#61; Math.min(dp[i - 1][j], dp[i][j - 1]) &#43; 1;
        }
      }
    }

    return dp[m][n];
  }
}
</code></pre> 
<h5>动态规划&#43;压缩数组&#xff08;可以对比上面代码进行理解&#xff09;</h5> 
<pre><code class="language-java">import java.util.Scanner;

public class Main {
  static String A;
  static String B;
  static int m;
  static int n;

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    A &#61; sc.next();
    B &#61; sc.next();

    m &#61; B.length();
    n &#61; A.length();

    System.out.println(getResult());
  }

  public static int getResult() {
    // 初始时preRow记录第一行上各点到(0,0)点的最短距离&#xff0c;即为(0,0) -&gt; (0,j) 的直线路径
    int[] preRow &#61; new int[n &#43; 1];
    for (int j &#61; 0; j &lt;&#61; n; j&#43;&#43;) {
      preRow[j] &#61; j;
    }

    // 初始时curRow记录第二行上各点到(0,0)点的最短距离
    int[] curRow &#61; new int[n &#43; 1];

    for (int i &#61; 1; i &lt;&#61; m; i&#43;&#43;) {
      // curRow[0]是指 (i, 0)点 到 (0,0)点 的最短距离&#xff0c;即为(0,0) -&gt; (i, 0) 的直线路径
      curRow[0] &#61; i;

      for (int j &#61; 1; j &lt;&#61; n; j&#43;&#43;) {
        if (A.charAt(j - 1) &#61;&#61; B.charAt(i - 1)) {
          // 如果可以走斜线&#xff0c;则选走斜线的点
          curRow[j] &#61; preRow[j - 1] &#43; 1;
        } else {
          // 如果不能走斜线&#xff0c;则从当前点的上方点、左方点中选择一个较小值
          curRow[j] &#61; Math.min(preRow[j], curRow[j - 1]) &#43; 1;
        }
      }

      // 压缩
      System.arraycopy(curRow, 0, preRow, 0, n &#43; 1);
    }

    return curRow[n];
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<h5>动态规划解法&#xff08;下面解法会超出内存限制&#xff0c;但是好理解&#xff0c;是后面一种压缩数组解法的基础&#xff09;</h5> 
<pre><code class="language-python"># 输入获取
A, B &#61; input().split()
m, n &#61; len(B), len(A)


# 算法入口
def getResult():
    # dp[i][j] 记录的是(0,0)到达点(i, j)的最短路径
    dp &#61; [[0] * (n &#43; 1) for _ in range(m &#43; 1)]

    # (0,0)到达矩阵第一行上的各点的最短路径&#xff0c;即为(0,0) -&gt; (0,j) 的直线路径
    for j in range(n &#43; 1):
        dp[0][j] &#61; j

    # (0,0)到达矩阵第一列上的各点的最短路径&#xff0c;即为(0,0) -&gt; (i,0) 的直线路径
    for i in range(m &#43; 1):
        dp[i][0] &#61; i

    for i in range(1, m &#43; 1):
        for j in range(1, n &#43; 1):
            if A[j - 1] &#61;&#61; B[i - 1]:
                # 如果可以走斜线&#xff0c;则选走斜线的点
                dp[i][j] &#61; dp[i - 1][j - 1] &#43; 1
            else:
                # 如果不能走斜线&#xff0c;则从当前点的上方点、左方点中选择一个较小值
                dp[i][j] &#61; min(dp[i - 1][j], dp[i][j - 1]) &#43; 1

    return dp[m][n]


# 算法调用
print(getResult())
</code></pre> 
<h5>动态规划&#43;压缩数组&#xff08;可以对比上面代码进行理解&#xff09;</h5> 
<pre><code class="language-python"># 输入获取
A, B &#61; input().split()
m, n &#61; len(B), len(A)


# 算法入口
def getResult():
    # 初始时preRow记录第一行上各点到(0,0)点的最短距离&#xff0c;即为(0,0) -&gt; (0,j) 的直线路径
    preRow &#61; [i for i in range(n &#43; 1)]

    # 初始时curRow记录第二行上各点到(0,0)点的最短距离
    curRow &#61; [0] * (n &#43; 1)

    for i in range(1, m &#43; 1):
        # curRow[0]是指 (i, 0)点 到 (0,0)点 的最短距离&#xff0c;即为(0,0) -&gt; (i, 0) 的直线路径
        curRow[0] &#61; i

        for j in range(1, n &#43; 1):
            if A[j - 1] &#61;&#61; B[i - 1]:
                # 如果可以走斜线&#xff0c;则选走斜线的点
                curRow[j] &#61; preRow[j - 1] &#43; 1
            else:
                # 如果不能走斜线&#xff0c;则从当前点的上方点、左方点中选择一个较小值
                curRow[j] &#61; min(preRow[j], curRow[j - 1]) &#43; 1

        # 压缩
        for j in range(n &#43; 1):
            preRow[j] &#61; curRow[j]

    return curRow[n]


# 算法调用
print(getResult())
</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<h5>动态规划解法&#xff08;下面解法会超出内存限制&#xff0c;但是好理解&#xff0c;是后面一种压缩数组解法的基础&#xff09;</h5> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;math.h&gt;

int main() {
    char A[10000];
    scanf(&#34;%s&#34;, A);

    char B[10000];
    scanf(&#34;%s&#34;, B);

    int m &#61; (int) strlen(B);
    int n &#61; (int) strlen(A);

    // dp[i][j] 记录的是(0,0)到达点(i, j)的最短路径
    int dp[m &#43; 1][n &#43; 1];

    // (0,0)到达矩阵第一行上的各点的最短路径&#xff0c;即为(0,0) -&gt; (0,j) 的直线路径
    for (int j &#61; 0; j &lt;&#61; n; j&#43;&#43;) {
        dp[0][j] &#61; j;
    }

    // (0,0)到达矩阵第一列上的各点的最短路径&#xff0c;即为(0,0) -&gt; (i,0) 的直线路径
    for (int i &#61; 0; i &lt;&#61; m; i&#43;&#43;) {
        dp[i][0] &#61; i;
    }

    for (int i &#61; 1; i &lt;&#61; m; i&#43;&#43;) {
        for (int j &#61; 1; j &lt;&#61; n; j&#43;&#43;) {
            if (A[j - 1] &#61;&#61; B[i - 1]) {
                // 如果可以走斜线&#xff0c;则选走斜线的点
                dp[i][j] &#61; dp[i - 1][j - 1] &#43; 1;
            } else {
                // 如果不能走斜线&#xff0c;则从当前点的上方点、左方点中选择一个较小值
                dp[i][j] &#61; (int) fmin(dp[i - 1][j], dp[i][j - 1]) &#43; 1;
            }
        }
    }

    printf(&#34;%d&#34;, dp[m][n]);

    return 0;
}</code></pre> 
<h5>动态规划&#43;压缩数组&#xff08;可以对比上面代码进行理解&#xff09;</h5> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;math.h&gt;

int main() {
    char A[10000];
    scanf(&#34;%s&#34;, A);

    char B[10000];
    scanf(&#34;%s&#34;, B);

    int m &#61; (int) strlen(B);
    int n &#61; (int) strlen(A);

    // 初始时preRow记录第一行上各点到(0,0)点的最短距离&#xff0c;即为(0,0) -&gt; (0,j) 的直线路径
    int preRow[n &#43; 1];
    for (int j &#61; 0; j &lt;&#61; n; j&#43;&#43;) {
        preRow[j] &#61; j;
    }

    // 初始时curRow记录第二行上各点到(0,0)点的最短距离
    int curRow[n &#43; 1];

    for (int i &#61; 1; i &lt;&#61; m; i&#43;&#43;) {
        // curRow[0]是指 (i, 0)点 到 (0,0)点 的最短距离&#xff0c;即为(0,0) -&gt; (i, 0) 的直线路径
        curRow[0] &#61; i;

        for (int j &#61; 1; j &lt;&#61; n; j&#43;&#43;) {
            if (A[j - 1] &#61;&#61; B[i - 1]) {
                // 如果可以走斜线&#xff0c;则选走斜线的点
                curRow[j] &#61; preRow[j - 1] &#43; 1;
            } else {
                // 如果不能走斜线&#xff0c;则从当前点的上方点、左方点中选择一个较小值
                curRow[j] &#61; (int) fmin(preRow[j], curRow[j - 1]) &#43; 1;
            }
        }

        // 压缩
        for (int j &#61; 0; j &lt;&#61; n; j&#43;&#43;) preRow[j] &#61; curRow[j];
    }

    printf(&#34;%d&#34;, curRow[n]);

    return 0;
}</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>